#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "Stack.h"
//插入函数
void InsertSort(int* arr, int N)
{
	for (int i = 0; i < N - 1; i++)
	{
		int end = i;
		//即将排序的元素，保留在tmp
		int tmp = arr[end + 1];
		//end>=0代表还有元素未比较
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//来到这里分为两种情况 
		//1：break->遇到比元素tmp小或和tmp相等的，将m放在它的后面
		//2：全部比较完了，都没有遇到<=tmp的，最后tmp放在数组第一个位置
		arr[end + 1] = tmp;
	}

}
//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
//三数取中
int GetMidi(int* a, int left, int right)
{
	// 计算中间元素的下标
	int mid = (left + right) / 2;

	// 比较三个元素：left, mid, right
	// 首先比较left和mid
	if (a[left] < a[mid])
	{
		// 如果left < mid，再比较mid和right
		if (a[mid] < a[right])
		{
			// 如果left < mid < right，则mid是中间值
			return mid;
		}
		else if (a[left] > a[right])  // 如果left > right，则mid是最大值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left < right，则right是中间值
			return right;
		}
	}
	else // 如果a[left] > a[mid]
	{
		// 比较mid和right
		if (a[mid] > a[right])
		{
			// 如果mid > right，则mid是中间值
			return mid;
		}
		else if (a[left] < a[right]) // 如果left < right，则mid是最小值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left > right，则right是中间值
			return right;
		}
	}
}
//全部忘加[],第二个写成if

//第一种单趟：霍尔法
int PartSort1(int* a, int left, int right)
{
	// 使用三数取中法获取基准元素的正确位置
	int Mid = GetMidi(a, left, right);
	// 将基准元素交换到数组的最左边
	Swap(&a[left], &a[Mid]);
	// 设置基准元素的索引为keyi
	int keyi = left;

	// 当left小于right时，进行单趟排序
	while (left < right)
	{
		// 从右向左扫描，找到第一个小于基准元素的值
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		// 注意，这里使用&&连接两个条件，并且顺序很重要，
		// 因为如果left >= right，我们就不再需要继续比较
		// 此时a[right] >= a[keyi]放在前面的话，会越界访问

		// 从左向右扫描，找到第一个大于基准元素的值
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		// 交换两个元素，将大于基准的元素放到右边，小于基准的元素放到左边
		Swap(&a[left], &a[right]);
	}

	// 最后，将基准元素放到正确的位置（left此时指向的位置）
	Swap(&a[keyi], &a[left]);
	// 返回基准元素的最终位置
	return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{
	// 使用三数取中法获取基准元素的正确位置
	int Mid = GetMidi(a, left, right);
	// 将基准元素交换到数组的最左边
	Swap(&a[left], &a[Mid]);

	// 设置基准元素的值
	int key = a[left];
	// 设置基准元素的位置
	int hole = left;

	// 当left小于right时，进行单趟排序
	while (left < right)
	{
		// 从右向左扫描，找到第一个小于基准元素的值
		while (left < right && a[right] >= key)
		{
			--right;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[right];
		// 更新"坑"的位置
		hole = right;

		// 从左向右扫描，找到第一个大于基准元素的值
		while (left < right && a[left] <= key)
		{
			++left;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[left];
		// 更新"坑"的位置
		hole = left;
	}

	// 最后，将基准元素放到正确的位置（hole此时指向的位置）
	a[hole] = key;
	// 返回基准元素的最终位置
	return hole;
}
////前后指针法
//int partsort3(int* a, int left, int right)
//{
//	int prev = left;
//	int cur = left + 1;
//
//	while (cur <= right)
//	{
//		if (a[cur] < a[left] && ++prev != cur)
//		{
//			Swap(&a[cur], &a[prev]);
//
//		}
//		cur++;
//	}
//	Swap(&a[prev], &a[left]);
//	//最后比left元素小的 都集中在了prev的下面及其左面，此时prev和left交换，最左面的元素一定是来到了正确的位置
//	return prev;
//	//a[cur] < a[left] 后 cur肯定是要++的，
//	//如果此时prev+1 = cur就代表prev和cur之间还没有比下标为left的元素大的元素，所以没必要交换，
//	//当++prev!=cur 的时候才交换，其次++prev!=cur 不仅判断还+1了，
//}
//第三种单趟：前后指针法
//int  partsort3(int* a, int left, int right)
//{
//	int Mid = GetMidi(a, left, right);
//	Swap(&a[left], &a[Mid]);
//
//	int prev = left;
//	int cur = prev + 1;
//	int keyi = left;
//
//	while (cur <= right)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[cur], &a[prev]);
//
//		}
//		cur++;
//	}
//	Swap(&a[prev], &a[keyi]);
//	return prev;
//}
//前后指针法
int PartSort3(int* a, int left, int right)
{
	// 1. 获取基准值
	int midi = GetMidi(a, left, right);
	// 将基准值与数组的第一个元素交换，确保基准值位于起始位置
	Swap(&a[left], &a[midi]);

	// 2. 初始化指针
	int prev = left; // 设置前指针prev为起始位置
	int cur = prev + 1; // 设置后指针cur为起始位置的后一个元素

	int keyi = left;

	// 3. 单趟排序
	while (cur <= right)
	{
		// 4. 比较和交换
		if (a[cur] < a[keyi] && ++prev != cur) // 如果后指针cur所指向的元素小于基准值
		{
			Swap(&a[prev], &a[cur]); // 并且前指针prev还没有到达cur的位置，
			// 则将前指针向前移动一位，并与后指针指向的元素交换
		}

		// 5. 移动指针
		++cur; // 继续移动后指针cur
	}

	// 6. 交换基准值
	Swap(&a[prev], &a[keyi]);

	// 7. 返回基准值位置
	return prev;
}

//递归快排(霍尔)
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = PartSort1(a, left, right);

	QuickSort1(a, left, keyi - 1);
	QuickSort1(a, keyi + 1, right);

}
//递归快排（挖坑）
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = PartSort2(a, left, right);

	QuickSort2(a, left, keyi - 1);
	QuickSort2(a, keyi + 1, right);

}
//递归快排（前后指针）
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = PartSort3(a, left, right);

	QuickSort3(a, left, keyi - 1);
	QuickSort3(a, keyi + 1, right);

}

//优化递归快排(霍尔)
void QuickSort4(int* a, int left, int right)
{
	if (left >= right)
		return;

	if ((right - left + 1) > 10)
	{
		int keyi = PartSort1(a, left, right);

		QuickSort4(a, left, keyi - 1);
		QuickSort4(a, keyi + 1, right);

	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
	//左面确认起点，右面确认个数
}
//优化递归快排(挖坑)
void QuickSort5(int* a, int left, int right)
{
	if (left >= right)
		return;

	if ((right - left + 1) > 10)
	{
		int keyi = PartSort1(a, left, right);

		QuickSort5(a, left, keyi - 1);
		QuickSort5(a, keyi + 1, right);

	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
	//左面确认起点，右面确认个数
}
//优化递归快排（前后指针）
void QuickSort6(int* a, int left, int right)
{
	if (left >= right)
		return;

	if ((right - left + 1) > 10)
	{
		int keyi = PartSort1(a, left, right);

		QuickSort6(a, left, keyi - 1);
		QuickSort6(a, keyi + 1, right);

	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
	//左面确认起点，右面确认个数
}
//非递归快排，借助栈
void  QuickSortNoneR(int* a, int left, int right)
{
	// 1. 初始化栈
	ST st;
	STInit(&st);

	// 2. 入栈：将right和left的值分别入栈
	STPush(&st, right);
	STPush(&st, left);

	// 3. 栈不为空时继续处理
	while (!STEmpty(&st))
	{
		// 4. 出栈：从栈顶取出begin和end的值
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		// 5. 调用PartSort1函数获取基准值的位置
		int keyi = PartSort1(a, begin, end);

		// 6. 入栈：根据keyi的位置，将右半部分和左半部分的起始位置入栈
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (keyi - 1 > begin)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	// 7. 销毁栈
	STDestroy(&st);
}
//非递归快排(借助栈)
//void QuickSortNoneR(int* a, int begin, int end)
//{
//	ST st;
//	STInit(&st);
//	STPush(&st, end);
//	STPush(&st, begin);
//	while (!STEmpty(&st))
//	{
//		int left = STTop(&st);
//		STPop(&st);
//
//		int right = STTop(&st);
//		STPop(&st);
//
//		int keyi = PartSort1(a, left, right);
//		// [lefy,keyi-1] keyi [keyi+1, right]
//		if (keyi + 1 < right)
//		{
//			STPush(&st, right);
//			STPush(&st, keyi + 1);
//		}
//
//		if (left < keyi - 1)
//		{
//			STPush(&st, keyi - 1);
//			STPush(&st, left);
//		}
//	}
//
//	STDestroy(&st);
//}
//测试少量快排


void Test1()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSortNoneR(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	//int* a8 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
	{
		a1[i] = rand() + i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		//a8[i] = a1[i];
	}

	int begin1 = clock();
	QuickSort1(a1, 0, N - 1);
	int end1 = clock();

	int begin2 = clock();
	QuickSort2(a2, 0, N - 1);
	int end2 = clock();

	int begin3 = clock();
	QuickSort3(a3, 0, N - 1);
	int end3 = clock();

	int begin4 = clock();
	QuickSort4(a4, 0, N - 1);
	int end4 = clock();


	int begin5 = clock();
	QuickSort5(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	QuickSort6(a6, 0, N - 1);
	int end6 = clock();

	int begin7 = clock();
	QuickSortNoneR(a7, 0, N - 1);
	int end7 = clock();

	/*int begin8 = clock();
	QuickSort(a7, 0, N - 1);
	int end8 = clock();*/



	printf("递归快排（霍尔):%d\n", end1 - begin1);
	printf("递归快排（挖坑):%d\n", end2 - begin2);
	printf("递归快排（前后指针):%d\n", end3 - begin3);

	printf("优化递归快排（霍尔):%d\n", end4 - begin4);
	printf("优化递归快排（挖坑):%d\n", end5 - begin5);
	printf("优化递归快排（前后指针):%d\n", end6 - begin6);
	printf("非递归快排（栈):%d\n", end7 - begin7);
	//printf("三路划分快排:%d\n", end8 - begin8);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	//free(a8);
}
int main()
{
	TestOP();

	return 0;
}

